home *** CD-ROM | disk | FTP | other *** search
/ Aminet 24 / Aminet 24 (1998)(GTI - Schatztruhe)[!][Apr 1998].iso / Aminet / dev / c / vbcc.lha / vbcc / loop.c < prev    next >
C/C++ Source or Header  |  1998-01-31  |  61KB  |  1,580 lines
  1. /*  $VER: vbcc (loop.c) V0.4     */
  2. /*  schleifenorientierte Optimierungen  */
  3.  
  4. #include "opt.h"
  5.  
  6. static char FILE_[]=__FILE__;
  7.  
  8. #define MOVE_IC 1
  9. #define MOVE_COMP 2
  10.  
  11. /*  Liste, in die ICs eingetragen werden, die aus Schleifen */
  12. /*  gezogen werden sollen.                                  */
  13. struct movlist{
  14.     struct movlist *next;
  15.     struct IC *IC;
  16.     struct flowgraph *target_fg;
  17.     int flags;
  18. };
  19.  
  20. struct movlist *first_mov,*last_mov;
  21.  
  22. int report_weird_code,report_suspicious_loops;
  23.  
  24. /*  Bitvektoren fuer schleifeninvariante ICs    */
  25. unsigned char *invariant,*inloop,*moved,*moved_completely;
  26. unsigned char *fg_tmp;
  27. unsigned char *not_movable;
  28. size_t bsize;
  29.  
  30.  
  31. /*  Liste, in die ICs fuer strength-reduction eingetragen   */
  32. /*  werden.                                                 */
  33. struct srlist{
  34.     struct srlist *next;
  35.     struct IC *ind_var;
  36.     struct IC *IC;
  37.     struct flowgraph *target_fg;
  38.     /*  Hilfsvariable, falls eine aequivalente Operation schon reduziert    */
  39.     /*  wurde.                                                              */
  40.     struct Var *hv;
  41. };
  42.  
  43. struct srlist *first_sr,*last_sr;
  44.  
  45. /*  Liste, in die Daten fuer loop-unrolling eingetragen werden. */
  46. struct urlist{
  47.     int flags;
  48.     long total,unroll;
  49.     struct IC *cmp,*branch,*ind;
  50.     struct flowgraph *start,*head;
  51.     struct urlist *next;
  52. } *first_ur;
  53.  
  54. #define UNROLL_COMPLETELY 1
  55. #define UNROLL_MODULO 2
  56. #define UNROLL_INVARIANT 3
  57.  
  58. /*  Hier werden Induktionsvariablen vermerkt    */
  59. struct IC **ind_vars;
  60.  
  61. static struct flowgraph *first_fg;
  62.  
  63. int loops(struct flowgraph *fg,int footers)
  64. /*  kennzeichnet Schleifen im Flussgraph; wenn footers!=0 werden darf eine  */
  65. /*  Schleife nur einen gemeinsamen Austrittspunkt haben                     */
  66. {
  67.     int i,start,end,c=0;struct flowlist *lp;struct flowgraph *g,*loopend;
  68.     if(DEBUG&1024) printf("searching loops\n");
  69.     g=fg;
  70.     while(g){
  71.         start=g->index;
  72.         end=-1;
  73.         for(lp=g->in;lp;lp=lp->next){
  74.             if(!lp->graph) continue;
  75.             if(lp->graph->branchout==g||!lp->graph->end||lp->graph->end->code!=BRA){
  76.                 i=lp->graph->index;
  77.                 if(i>=start&&i>end){ end=i;loopend=lp->graph; }
  78.             }
  79.         }
  80.         if(end>=0){
  81.         /*  Schleife oder etwas aehnliches  */
  82.             struct flowgraph *p=g;
  83.             if(DEBUG&1024) printf("found possible loop from blocks %d to %d\n",start,end);
  84.             if(1/*goto_used*/){
  85.                 if(DEBUG&1024) printf("have to check...\n");
  86.                 do{
  87.                     if(!p||p->index>end) break;
  88.  
  89.                     /*  testen, ob aus der Schleife gesprungen wird */
  90.                     if(p->branchout&&footers){
  91.                         i=p->branchout->index;
  92.                         if(i<start){
  93.                             end=-1;
  94.                             break;
  95.                         }
  96.                         if(i>end&&(DEBUG&1024)){
  97.                             puts("jump out of loop");
  98.                             if(p->branchout!=loopend->normalout){
  99.                                 puts("no break");
  100.                                 if(p->branchout->start->typf!=return_label) puts("no return");
  101.                             }
  102.                         }
  103.                         if(i>end&&p->branchout!=loopend->normalout&&p->branchout->start->typf!=return_label){
  104.                         /*  Sprung zu anderem als dem normalen Austritt oder return */
  105.                             end=-1;
  106.                             break;
  107.                         }
  108.                     }
  109.                     /*  testen, ob in die Schleife gesprungen wird  */
  110.                     if(p!=g){
  111.                         for(lp=p->in;lp;lp=lp->next){
  112.                             if(!lp->graph) continue;
  113.                             if(lp->graph->branchout==p){
  114.                                 i=lp->graph->index;
  115.                                 if(i<start){
  116.                                     if(report_weird_code){error(175);report_weird_code=0;}
  117.                                     end=-1;
  118.                                     break;
  119.                                 }
  120.                                 if(i>end){
  121.                                     end=-1;
  122.                                     break;
  123.                                 }
  124.                             }
  125.                         }
  126.                     }
  127.                     if(p->index==end) break;
  128.                     p=p->normalout;
  129.                 }while(end>=0);
  130.             }else{
  131.                 if(DEBUG&1024) printf("must be a loop, because there was no goto\n");
  132.             }
  133.         }
  134.         if(end>=0){
  135.             if(DEBUG&1024) printf("confirmed that it is a loop\n");
  136.             g->loopend=loopend;
  137.             c++;
  138.         }
  139.         g=g->normalout;
  140.     }
  141.     return(c);
  142. }
  143.  
  144. struct flowgraph *create_loop_headers(struct flowgraph *fg,int av)
  145. /*  Fuegt vor jede Schleife einen Kopf-Block ein, wenn noetig.  */
  146. /*  Wenn av!=0 werden aktive Variablen korrekt uebertragen und  */
  147. /*  diverse Registerlisten uebernommen und index=-1 gesetzt.    */
  148. /*  Kann einen Block mehrmals in der ->in Liste eintragen       */
  149. {
  150.     struct flowgraph *g,*last,*new,*rg=fg;
  151.     struct IC *lic,*lastic;
  152.     if(DEBUG&1024) printf("creating loop-headers\n");
  153.     g=fg;last=0;lastic=0;
  154.     while(g){
  155.         new=0;
  156.         if(g->loopend){
  157.             if(!last){
  158.                 struct flowlist *lp;
  159.                 new=mymalloc(sizeof(struct flowgraph));
  160.                 rg=new;
  161.                 new->in=0;
  162.                 new->start=new->end=0;
  163.                 lp=mymalloc(sizeof(struct flowlist));
  164.                 lp->graph=new;
  165.                 lp->next=g->in;
  166.                 g->in=lp;
  167.             }else{
  168.                 struct flowlist *lp,*nl,**ls;
  169.                 new=mymalloc(sizeof(struct flowgraph));
  170.                 last->normalout=new;
  171.                 lic=mymalloc(ICS);
  172.                 lic->line=0;
  173.                 lic->file=0;
  174.                 new->start=new->end=lic;
  175.                 lic->code=LABEL;
  176.                 lic->typf=++label;
  177.                 lic->q1.flags=lic->q2.flags=lic->z.flags=0;
  178.                 lic->q1.am=lic->q2.am=lic->z.am=0;
  179.                 lic->use_cnt=lic->change_cnt=0;
  180.                 lic->use_list=lic->change_list=0;
  181.                 if(lastic) lastic->next=lic;
  182.                     else   first_ic=lic;
  183.                 lic->prev=lastic;
  184.                 g->start->prev=lic;
  185.                 lic->next=g->start;
  186.                 lp=g->in;ls=&new->in;
  187.                 while(lp){
  188.                     if(lp->graph&&lp->graph->index<g->index){
  189.                     /*  Eintritt von oben soll in den Kopf  */
  190.                         nl=mymalloc(sizeof(struct flowlist));
  191.                         nl->graph=lp->graph;
  192.                         nl->next=0;
  193.                         (*ls)=nl;
  194.                         ls=&nl->next;
  195.                         if(lp->graph->branchout==g){
  196.               struct IC *p=lp->graph->end;
  197.               if(DEBUG&1024) printf("changing branch\n");
  198.               while(p&&p->code==FREEREG) p=p->prev;
  199.               if(!p||p->code<BEQ||p->code>BRA) ierror(0);
  200.               p->typf=lic->typf;
  201.               lp->graph->branchout=new;
  202.                         }
  203.                         lp->graph=new;
  204.                     }
  205.                     lp=lp->next;
  206.                 }
  207.                 if(!new->in) ierror(0);
  208.             }
  209.             if(new){
  210.                 if(DEBUG&1024) printf("must insert loop-header before block %d\n",g->index);
  211.                 basic_blocks++;
  212.                 new->branchout=0;
  213.                 new->loopend=0;
  214.                 if(av)
  215.                     new->index=-1;
  216.                 else
  217.                     new->index=basic_blocks;
  218.                 new->normalout=g;
  219.                 new->calls=0;
  220.                 new->loop_calls=0;
  221.                 new->rd_in=new->rd_out=new->rd_kill=new->rd_gen=0;
  222.                 new->ae_in=new->ae_out=new->ae_kill=new->ae_gen=0;
  223.                 new->cp_in=new->cp_out=new->cp_kill=new->cp_gen=0;
  224.                 if(!av){
  225.                     new->av_in=new->av_out=new->av_kill=new->av_gen=0;
  226.                 }else{
  227.                     new->av_in=mymalloc(vsize);
  228.                     new->av_out=mymalloc(vsiz